#include <stdio.h>
#include <stdlib.h>

typedef char VertexType;			/* 顶点类型由用户定义 */
typedef int  EdgeType;				/* 边上的权值类型应由用户定义 */
#define MAXVEX 9					/* 最大顶点数，应由用户定义 */
#define INFINITY 65535				/* 用65535来代表∞ */

typedef int Pathmatrix[MAXVEX];
typedef int ShortPathTable[MAXVEX];

typedef struct
{
	VertexType vexs[MAXVEX];		/* 顶点表 */
	EdgeType matrix[MAXVEX][MAXVEX];	/* 邻接矩阵，可看做边表 */
	int numVertexes, numEdges;		/* 图中当前的顶点数和边数 */
}MGraph;

void CreateMGraph(MGraph *G, VertexType vertex[MAXVEX], EdgeType edge[MAXVEX][MAXVEX])
{
    int i,j;
    for(i=0;i < MAXVEX; i++)
    {
        G->vexs[i] = vertex[i];
        for(j=0; j < MAXVEX; j++)
        {
            G->matrix[i][j] = edge[i][j];
        }
    }
    G->numEdges = 15;
    G->numVertexes = 9;
}

void ShortestPath_Dijkstra(MGraph G, int v0, Pathmatrix *P, ShortPathTable *D)
{
	int v, w, k, min;
	int final[MAXVEX];
	for (v = 0; v < G.numVertexes; ++v)
	{
		final[v] = 0;
		(*D)[v] = G.matrix[v0][v];
		(*P)[v] = 0;
	}
	(*D)[v0] = 0;
	final[v0] = 1;

	for (v = 0; v < G.numVertexes; ++v)
	{
		min = INFINITY;
		for (w = 0; w < G.numVertexes; ++w)
		{
			if (!final[w] && (*D)[w] < min)
			{
				k = w;
				min = (*D)[w];
			}
		}
		final[k] = 1;
		for (w = 0; w < G.numVertexes; ++w)
		{
			if (!final[w] && (min + G.matrix[k][w] < (*D)[w]))
			{
				(*D)[w] = min + G.matrix[k][w];
				(*P)[w] = k;
			}
		}
	}
}

int main()
{
    int i,j;
    VertexType vertex[MAXVEX] = {'0','1','2','3','4','5','6','7','8'};
    EdgeType edge[MAXVEX][MAXVEX] =
    {
        {0, 1, 5, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY},
        {1, 0, 3, 7, 5, INFINITY, INFINITY, INFINITY, INFINITY},
        {5, 3, 0, INFINITY, 1, 7, INFINITY, INFINITY, INFINITY},
        {INFINITY, 7, INFINITY, 0, 2, INFINITY, 3, INFINITY, INFINITY},
        {INFINITY, 5, 1, 2, 0, 3, 6, 9, INFINITY},
        {INFINITY, INFINITY, 7, INFINITY, 3, 0, INFINITY, 5, INFINITY},
        {INFINITY, INFINITY, INFINITY, 3, 6, INFINITY, 0, 2, 7},
        {INFINITY, INFINITY, INFINITY, INFINITY, 9, 5, 2, 0, 4},
        {INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 7, 4, 0}
    };
    MGraph G;
    CreateMGraph(&G, vertex, edge);
    Pathmatrix P;
    ShortPathTable D;

    ShortestPath_Dijkstra(G, 0, P, D);
    i = 8;
    printf("%d    ",i);
    do
    {
        i = P[i];
        printf("%d    ",i);
    }while(i>0);

    return 0;
}










